#include<iostream>
using namespace std;
//#include<algorithm>
//#include<list>
#include<vector>
#include<string>
#include<stack>

//150.i逆波兰表达式求值
//https://leetcode.cn/problems/evaluate-reverse-polish-notation/
//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        stack<int> st;
//        for (auto& str : tokens)
//        {
//            if (str[0] == '+' || str[0] == '-' || str[0] == '*' || str[0] == '/' && str.size() == 1 )
//            {
//                int last = st.top();
//                st.pop();
//                int first = st.top();
//                st.pop();
//                switch (str[0])
//                {
//                case '+':
//                    st.push(first + last);
//                    break;
//                case '-':
//                    st.push(first - last);
//                    break;
//                case '*':
//                    st.push(first * last);
//                    break;
//                case '/':
//                    st.push(first / last);
//                    break;
//                }
//            }
//            else
//            {
//                st.push(stoi(str.c_str()));
//            }
//        }
//        return st.top();
//    }
//};

//C++11语法解法
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        map<string, function<int(int, int)>> m = {
            {"+",[](int a,int b) {return a + b; }},
            {"-",[](int a,int b) {return a - b; }},
            {"*",[](int a,int b) {return a * b; }},
            {"/",[](int a,int b) {return a / b; }},
        };

        for (const auto& c : tokens)
        {
            if (m.count(c)) //如果是运算符
            {
                int r = st.top();
                st.pop();
                int l = st.top();
                st.pop();
                st.push(m[c](l, r));
            }
            else
            {
                // int num = 0;
                // int oper = 1;
                // int begin = c.size() - 1;
                // int end = 0;
                // if (c[0] == '-')
                // {
                //     oper = -1;
                //     end = 1;
                // }
                // int mult = 1;
                // while(begin >= end)
                // {
                //     num += mult * oper * (c[begin] - '0');
                //     mult *= 10;
                //     --begin;
                // }
                // st.push(num);
                st.push(stoi(c));
            }
        }
        return st.top();
    }
};







//215.数组中第K个大的元素
//https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};